package LeetCode.interview;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import com.sun.javafx.image.IntPixelAccessor;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题　
	Description:
	
	Count the number of prime numbers less than a non-negative number, n.
	
	Credits:
	Special thanks to @mithmatt for adding this problem and creating all test cases.
题目大意
	　
　	计算少于非负数的质数数，n。
解题思路
	//学习C语言时判断一个数是否为素数
	bool isPrime(int num)   {
	    int s = sqrt(num) + 1;
	    for( int i = 3; i != s; ++i)   {
	        if (num mode i == 0)
	            return false;
	    }
	    return true;
	}
	
		我们知道2是最小的质数，那么2的倍数均不为质数（因为它们可以分解为一个数*2），所以我们可以将小于n的数中2的倍数，全部排除掉。
		排除掉2的整数倍后，剩下的数中大于2的最小的数就是下一个质数，也就是3.
		同样我们可以排除掉小于n的数中3的整数倍的数，得到下一个质数为5.
	参考资料：http://blog.csdn.net/angelazy/article/details/45561885
	如果一个数是另一个数的倍数，那这个数肯定不是素数。利用这个性质，我们可以建立一个素数数组，
		从2开始将素数的倍数都标注为不是素数。
			第一轮将4、6、8等表为非素数，然后遍历到3，发现3没有被标记为非素数，
			则将6、9、12等标记为非素数，一直到N为止，再数一遍素数数组中有多少素数。
	
 * @Date 2017-09-14 23：43
 */
public class _204_Count_Primes {
	
	public int countPrimes(int n) {
		//质数数组
		boolean[] prime = new boolean[n];
		Arrays.fill(prime, true);
		//数学上：0和1都不是质数
		for (int i = 2; i < n; i ++) {
			if (prime[i]) {
				//将i的倍数全部标记为非质数
				//从2倍开始(每加一次i,就是加一倍)
				for (int j = i*2; j < n; j+=i) {
					prime[j] = false;
				}
			}
		}
		//统计有几个质数
		int count = 0;
		for (int i = 2; i < prime.length; i ++) {
			if (prime[i])	count++;	
		}
		return count;
	}
	public void traverse(int[] nums) {
		for (int i : nums) {
			LogUtils.print(i);
		}
	}
    
	public static void main(String[] args) {
		_204_Count_Primes obj = new _204_Count_Primes();
		LogUtils.println("", Math.sqrt(0));
	}

}
